package str;

import java.util.*;
import java.util.stream.Collectors;

/**
 * leet-code(1436) 旅行终点站
 *
 * @author Ringo
 * @date 2021/10/1 9:13
 */
public class DestCity {

    public static void main(String[] args) {
        List<List<String>> paths = new ArrayList<>();
        paths.add(Arrays.asList("B", "C"));
        paths.add(Arrays.asList("D", "B"));
        paths.add(Arrays.asList("C", "A"));
        System.out.println(destCity1(paths));
        System.out.println(destCity2(paths));
        System.out.println(destCity3(paths));
    }

    // 参照答案后做一些修改（速度有点慢）
    public static String destCity3(List<List<String>> paths) {
        // 起点集
        Set<String> srcSet = paths.stream().map(path -> path.get(0)).collect(Collectors.toSet());
        // 终点
        Set<String> destSet = paths.stream().map(path -> path.get(1)).collect(Collectors.toSet());
        // 起点集中不会包括终点
        return destSet.stream().filter(end -> !srcSet.contains(end)).findFirst().orElse("");
    }

    // 参照官方答案
    public static String destCity2(List<List<String>> paths) {
        // 起点集
        Set<String> src = new HashSet<>();
        paths.forEach(path -> src.add(path.get(0)));

        // 起点集中不会包括终点
        for (List<String> path : paths) {
            if (!src.contains(path.get(1))) {
                return path.get(1);
            }
        }

        return null;
    }

    // 自己写的
    public static String destCity1(List<List<String>> paths) {
        // 起点集
        Set<String> src = new HashSet<>();
        // 终点集
        Set<String> dest = new HashSet<>();

        paths.forEach(path -> {
            src.add(path.get(0));
            dest.add(path.get(1));
        });

        dest.removeAll(src);    // 求差集

        Iterator<String> iterator = dest.iterator();
        return iterator.hasNext() ? iterator.next() : null;
    }
}
